package leetcode.leetcode.editor.cn;//一条包含字母 A-Z 的消息通过以下方式进行了编码：
//
// 'A' -> 1
//'B' -> 2
//...
//'Z' -> 26
// 
//
// 给定一个只包含数字的非空字符串，请计算解码方法的总数。 
//
// 示例 1: 
//
// 输入: "12"
//输出: 2
//解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
// 
//
// 示例 2: 
//
// 输入: "226"
//输出: 3
//解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
// 
// Related Topics 字符串 动态规划

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public static void main(String[] args) {
        new Solution().numDecodings("00");
    }

    public int numDecodings(String s) {
        int length = s.length();
        if (length == 1) {
            return s.charAt(0) == '0' ? 0 : 1;
        }
        int[] res = new int[length];
        fillTwo(s, res);
        for (int i = 2; i < length; i++) {

            int num = (s.charAt(length - i - 1) - '0') * 10 + s.charAt(length - i) - '0';
            if (num == 10 || num == 20) {
                res[i] = res[i - 2];
            } else if (num > 26) {
                res[i] = res[i - 1];
            } else {
                res[i] = res[i - 2] + res[i - 1];
            }
        }
        return res[length - 1];
    }

    private void fillTwo(String s, int[] res) {
        int length = s.length();
        if (s.charAt(length - 2) == '0') {
            res[0] = 0;
            res[1] = 0;
            return;
        }
        if (s.charAt(length - 1) == '0') {
            res[0] = 0;
        } else {
            res[0] = 1;
        }
        int num = (s.charAt(length - 2) - '0') * 10 + s.charAt(length - 1) - '0';
        if (num == 10 || num == 20) {
            res[1] = 1;
        } else if (num % 10 == 0) {
            res[1] = 0;
        } else if (num <= 26) {
            res[1] = 2;
        } else {
            res[1] = 1;
        }
    }

    private int numDecodings(String s, int index) {
        if (s.charAt(index) == '0') {
            return 0;
        }
        int next = index + 1;
        int nextTow = index + 2;
        int length = s.length();
        if (next == length) {
            return 1;
        }
        int num = (s.charAt(index) - '0') * 10 + s.charAt(next) - '0';
        if (nextTow == length) {
            if (num == 10 || num == 20) {
                return 1;
            } else if (num <= 26) {
                return 2;
            } else if (num % 10 == 0) {
                return 0;
            } else {
                return 1;
            }
        }
        if (num == 10 || num == 20) {
            return numDecodings(s, nextTow);
        } else if (num > 26) {
            return numDecodings(s, next);
        } else {
            return numDecodings(s, next) + numDecodings(s, nextTow);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
